package shuanfa.exercise;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class exercise {
    //冒泡排序
    public void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    //插入排序
    public void insertSort(int[] arr) {
        int current, preIndex;
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];
            preIndex = i - 1;
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];//前一个节点后移
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    //希尔排序
    public void shellSort(int[] arr) {
        int current, preIndex;
        for (int step = arr.length / 2; step > 0; step = step / 2) {//逐步缩小增量
            for (int i = step; i < arr.length; i = i + step) {
                current = arr[i];
                preIndex = i - step;
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + step] = arr[preIndex];
                    preIndex = preIndex - step;
                }
                arr[preIndex + step] = current;
            }
        }
    }

    //快速排序
    public void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int start = arr[left];//定义第一个元素为初始值
            int low = left;
            int high = right;
            while (low < high) {
                while (low < high && arr[high] >= start) {
                    high--;
                }
                arr[low] = arr[high];
                while (low < high && arr[low] <= start) {
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = start;
            quickSort(arr, left, low - 1);
            quickSort(arr, low + 1, right);
        }
    }

    //归并排序
    public void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            //拆分
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);

            //合并
            merge(arr, left, mid, right, temp);
        }

    }

    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int l = left;
        int r = mid + 1;
        int t = 0;
        while (l <= mid && r <= right) {
            if (arr[l] < arr[right]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[r++];
            }
        }
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }

        //临时数组拷贝到原数组
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }

    //链表翻转 迭代
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next;
        ListNode cur = head;
        while (cur != null) {
            next = cur.next;//保存当前节点的下一个节点
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //链表翻转 递归
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        } else {
            ListNode reverseList = ReverseList(head.next);
            head.next.next = head;
            head.next = null;
            return reverseList;
        }
    }

    //倒数第K个值 递归实现
    public ListNode nToLast(ListNode head, int k, MyCount i) {
        ListNode listNode = nToLast(head.next, k, i);
        i.value = i.value + 1;//计数器+1
        if (i.value == k) {
            return head;
        }
        return listNode;
    }

    //迭代实现
    public ListNode kToLast(ListNode head, int k) {
        if (k <= 0) return null;
        ListNode left = head;
        ListNode right = head;
        for (int i = 0; i < k - 1; i++) {
            if (right == null) return null;
            right = right.next;
        }
        if (right == null) return null;
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        return left;
    }

    //爬楼梯 递归
    public int test(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return test(n - 1) + test(n - 2);
    }

    //爬楼梯 迭代
    public int test1(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int result = 0;
        int pre = 2;
        int prepre = 1;
        for (int i = 2; i < n; i++) {
            result = pre + prepre;
            prepre = pre;
            pre = result;
        }
        return result;
    }

    //合并两个有序数组 nums1.length = num1中有效元素+nums2中有效元素
    public void merge(int[] nums1, int[] nums2, int m, int n) {
        int length = m + n;
        for (int index = length - 1, nums1Index = m - 1, nums2Index = n - 1; index >= 0; index--) {
            if (nums1Index < 0) {
                nums1[index] = nums2[nums2Index--];
            } else if (nums2Index < 0) {
                break;
            } else if (nums1[nums1Index] < nums2[nums2Index]) {
                nums1[index] = nums2[nums2Index--];
            } else {
                nums1[index] = nums1[nums1Index--];
            }
        }
/*        int[] temp = new int[nums1.length];
        int i = 0,j =0;
        int length = nums2.length;
        int index = 0;
        while (j<length && i<nums1.length - length){
            if (nums1[i] <nums2[j]){
                temp[index++] = nums1[i++];
            }else {
                temp[index++] = nums2[j++];
            }
        }
        while (i<nums1.length - length){
            temp[index++] = nums1[i++];
        }
        while (j<length){
            temp[index++] = nums2[j++];
        }

        for (int k = 0; k < nums1.length; k++) {
            nums1[k] = temp[k];
        }
        return nums1;*/
    }

    //合并两个有序链表 循环+双指针法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        ListNode listNode1 = list1;
        ListNode listNode2 = list2;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val < listNode2.val) {
                p.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                p.next = listNode2;
                listNode2 = listNode2.next;
            }
            p = p.next;
        }
        if (listNode1 != null) {
            p.next = listNode1;
        }
        if (listNode2 != null) {
            p.next = listNode2;
        }
        return listNode.next;
    }

    //合并两个有序链表 递归法
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists1(list1.next, list2);
            return list1;
        }
        list2.next = mergeTwoLists1(list1, list2.next);
        return list2;
    }

    //删除排序链表重复元素 遍历法
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode currentNode = head;
        while (currentNode.next != null) {
            if (currentNode.next.val == currentNode.val) {
                currentNode.next = currentNode.next.next;
            } else {
                currentNode = currentNode.next;
            }
        }
        return head;
    }

    //删除排序链表重复元素 递归
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates1(head.next);
        if (head.next.val == head.val) {
            return head.next;
        } else {
            return head;
        }
    }

    //环形链表II
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slowPtr = head, fastPtr = head;
        boolean hasCycle = false;
        while (fastPtr.next != null && fastPtr.next.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr) {
                hasCycle = true;
                break;
            }
        }
        if (hasCycle) {
            fastPtr = head;
            while (fastPtr != slowPtr) {
                fastPtr = fastPtr.next;
                slowPtr = slowPtr.next;
            }
            return slowPtr;
        } else {
            return null;
        }
    }

    //回文链表
    public boolean isPalindrome(ListNode head) {
        ListNode slowP = head;
        ListNode fastP = head;
        while (fastP != null && fastP.next != null) {
            slowP = slowP.next;
            fastP = fastP.next.next;
        }
        if (fastP != null) {//奇数个节点 正中的归到左边
            slowP = slowP.next;
        }
        slowP = reverseList(slowP);
        fastP = head;
        while (slowP != null) {
            if (slowP.val != fastP.val) {
                return false;
            }
            slowP = slowP.next;
            fastP = fastP.next;
        }
        return true;
    }

    //字符串解码
    public String decodeString(String s) {
        LinkedList<String> linkedList = new LinkedList<>();
        return "";
    }

    //对称二叉树 递归实现
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return deepcheack(root.left, root.right);
    }

    public boolean deepcheack(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return deepcheack(left.left, right.right) && deepcheack(left.right, right.left);
    }

    //对称二叉树，队列迭代实现
    public boolean isSymmetric1(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return true;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) return true;
        queue.offer(left);
        queue.offer(right);
        while (!queue.isEmpty()){
            TreeNode l = queue.poll();
            TreeNode r = queue.poll();
            if (l== null && r ==null) continue;
            if (l==null || r== null) return false;
            if (l.val!=r.val) return false;
            queue.offer(l.left);
            queue.offer(r.right);
            queue.offer(l.right);
            queue.offer(r.left);
        }
        return true;
    }

    //二叉树最大深度，递归实现
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

    //二叉树最大深度，队列实现
    public int maxDepth1(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;//记录深度
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }

    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return helper(root) != -1;
    }
    public int helper(TreeNode node){
        if(node == null) return 0;
        int left = helper(node.left);
        int right = helper(node.right);
        if(left == -1 || right == -1 || Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right) + 1;//树的深度为左右子树最大深度+1

    }

    //有效的括号
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        for (char c:s.toCharArray()){
            if (c == '('){
                deque.push(')');
            }else if (c == '['){
                deque.push(']');
            }else if(c == '{'){
                deque.push('}');
            }else {
                if (deque.pop() != c || deque.isEmpty()){
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }



    public class MyCount {
        public int value = 0;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//用栈实现队列
class MyQueue {
    private static Stack<Integer> inStack;
    private static Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();

    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.peek();
    }

    public void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}